1. Field of the Invention
This invention relates to improvements in memory systems, and more particularly to improvements in a memory system of the type which enable automatic memory operations, in general, and garbage collection and reference counting, in particular, independently of a user processor with which it is associated.
2. Description of the Prior Art
The development of storage management systems has a long history with many related branches of research. Over the years, a great deal of attention has been given to the allocation and deallocation of memory structures. Many memory structures to this end are shown by H. M. Deitel, An Introduction to Operating Systems, Addison-Wesley, Mass., Chapter 7, 1982. Other major issues are discussed by D. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, Addison-Wesley, Reading, Mass., 1968.
The invention herein described is primarily concerned with garbage collected heap managed memories. Heap managed means that the memory is allocated and freed (either explicitly or implicitly) without regard to the temporal order or the size of the memory unit under consideration. A garbage collected memory is one in which usable memory is automatically reclaimed, and the memory may be reorganized from time to time to efficiently utilize the space of the memory, as needed. A background survey of garbage collection techniques and related background materials is presented by Cohen, J. "Garbage Collection of Linked Data Structures", Computing Surveys, Vol. 13, No. 3, September, 1981, pp. 341-367, and also by P. Bishop, "Garbage Collection in a Very Large Address Space", Massachusetts Institute of Technology, Working Paper 111, September, 1975.
Becoming of interest with the rapid development of artificial intelligence is the development of so-called "knowledge bases", large data bases, for use, for instance, in containing extremely large or complex information stores requiring dynamic organization. See, for example, Suwa, M., et al, "Knowledge Base Mechanisms", Preliminary Report on Fifth Generation Computer Systems, ICOT, 1980. Examples of some large data bases under consideration or implemented include, for instance, data bases which contain legal information, such as verbatim case reports, medical information for use in diagnosing possible diseases which present particular symptoms, certain patent information including abstracts, claims, and so forth. In such data bases, it is often desirable to search through sometimes millions of words and characters, then identify a particular record (case, patent, diagnosis, etc) related to the words and characters.
Presently, particular computer languages such as Lisp, and to a lesser extent, Pascal and Ada, are used to implement such heap allocated data bases (Lisp supporting garbage collected data bases, as well). In such traditional architectures where the memory allocation, de-allocation, garbage collection and compaction is provided, normally the language runtime support and the compiles used has the responsibility for the garbage collection and compaction, and if a virtual memory system is provided, it is normally the responsibility of the hardware and operating system to manage the virtual memory system. Typically, for example, the operating system will normally use some type of demand paged least recently used (LRU) scheme for determining how to move pages to and from the backing store, and the garbage collector specifies which pages will be needed or which will no longer be needed.
Among the key problems often encountered by programmers is the individual word access speed, which is related directly to the speed of the particular memory used. Also, the speed of allocation presents a difficult problem if memory units are not either last-in first-out (LIFO) allocated or of constant size. Additionally, the size of a virtual memory space is often of concern, since garbage collection costs increase with the size of the space being collected not with the amount of garbage being reclaimed. Finally, security or safety is a significant problem, since normally programs can ignore the actual structure of a memory organization, either intentionally or through inadvertence in program or memory design and blocks of data can easily be overwritten or obliterated entirely.
Typical memory systems with which the invention can be used, for example can be seen in copending patent applications by Oxley et al, entitled "COMPUTER MEMORY SYSTEM", Ser. No. 630,476, filed July 12, 1984 and by Thatte et al, entitled "COMPUTER SYSTEM ENABLING AUTOMATIC MEMORY OPERATIONS", Ser. No. 630,478, filed July 12, 1984, both of said applications being assigned to the assignee hereof and incorporated herein by reference.
In the operation of a typical memory system of the type described in said copending patent applications together with their associated user processors, the user processor requests the allocation of memory space as needed. Often, the allocation of the memory is done in a virtual address space. The allocation is often accomplished by apportioning the space from the beginning of the virtual address space to the end. As the virtual address space becomes fully allocated, eventually requests for additional space must be denied, until reusable space in the previously allocated virtual address space has been identified and reclaimed.
In the past, garbage collection techniques have been done typically by interrupting the processing being done by the user CPU, and running a garbage collection algorithm in the CPU to clean up the allocated virtual address space. As memories became larger and larger, typically the garbage collection process took more and more time, during all of which the main processing routine was not being run.
In recognition of this problem, "parallel" or "concurrent" garbage collection has been proposed, although to date, insofar as is known to applicants herein, true parallel garbage collection processing has not been actually achieved. In the consideration of parallel garbage collection processing, several terms need specific definition, as they are variously used in the art. As used herein, "parallel" garbage collection processing refers to garbage collection processing which is performed completely independently of the user processor and simultaneously with the user processor operation. (In the past, the term "parallel" with reference to garbage collection processing has included "concurrent".)
The term "concurrent" processing is used to mean garbage collection processing which is interleaved or time-shared with user CPU operations. Concurrent garbage collection, for instance, includes time shared accessing and processing operations, and may include garbage collection processing conducted by a single processor working alternately on garbage collection routines and regular operating routines.
It has been suggested by E. W. Dijkstra et al, "On-the-Fly Garbage Collection: An Exercise in Cooperation," Communications of the ACM, Vol. 21, No. 11 (Nov., 1978), pp. 966-975 to use a second processor for performing garbage collection, at least concurrently with the operation of the user processor (or the "mutator"). Another garbage collection method was suggested by G. L. Steele, "Multiprocessing compacting garbage collection," Communications of the ACM, Vol. 18, No. 9 (September 1975) pp. 495-508. In the Dijkstra process, allocated blocks are marked as being black, gray, or white, depending upon the use by the user program. The Steele process uses semaphores to mark the cells. Both processes, however, appear to require the participation of the user processor, at least in the marking of the cells used, and in operating in a timed concurrent manner with the garbage collection processor.
Another technique which has been used is by providing each block or cell in memory with a reference counter which provides an indication whether the block or cell is the subject of a pointer or reference from elsewhere. The assumption is made that if no reference is made to the block or cell, it is unreachable in the memory, is garbage, and therefore can be collected and the space reclaimed.
P. B. Bishop, supra, has suggested that garbage collection can be done in less than the entire virtual address space by performing garbage collection on areas into which the address space is broken. Each area maintains a list of pointers into the area so that entire address space need not be searched in determining references to cells or blocks within the area being collected.